// run: time -p $exec < input
// opt: 0
// flag: -g
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>

using pair = std::pair<long long, long long>;
std::vector<pair> v;
long long n, k, m;

void merge(std::vector<pair> & v)
{
	std::sort(v.begin(), v.end(), [](pair const & a, pair const & b) {
				return a.first < b.first || (a.first == b.first && a.second < b.second);
			});
	int n = v.size();
	for (int i = 0; i < n - 1; ) {
		if (v[i].second >= v[i + 1].first) {
			v[i].second = std::max(v[i].second, v[i + 1].second);
			n--;
			v.erase(v.begin() + i + 1);
		} else i++;
	}
}

std::vector<pair> put;

long long calc(pair const & p)
{
	long long ret = p.second - p.first + 1;
	for (auto i : put) {
		if (i.first <= p.first && i.second >= p.second) return 0;
		else if (i.first <= p.first && i.second >= p.first) ret -= i.second - p.first + 1;
		else if (i.second >= p.second && i.first <= p.second) ret -= p.second - i.first + 1;
	}
	return std::max(ret, 0ll);
}

int main()
{
	std::ios::sync_with_stdio(false);
	int T; std::cin >> T;
	while (T--) {
		std::cin >> n >> k >> m;
		v.clear();
		v.resize(n);
		for (int i = 0; i < n; i++) {
			std::cin >> v[i].first >> v[i].second;
			if (v[i].first > v[i].second) return 1;
		}
		merge(v);
		n = v.size();
		long long tans = 0;
		for (int ti = 0; ti < (1 << n); ti++) {
			long long ans = 0;
			put.clear();
			for (int i = 0; i < n; i++) {
				bool right = ti & (1 << n);
				long long len = v[i].second - v[i].first + 1;
				long long t = len / k;
				t = std::min(t, m);
				if (!right) {
					if (t) put.push_back({v[i].first, v[i].first + t * k - 1});
					v[i].first = std::min(v[i].second, v[i].first + t * k);
				} else {
					if (t) put.push_back({v[i].second - t * k + 1, v[i].second});
					v[i].second = std::max(v[i].second - t * k, v[i].first);
				}
				ans += t * k;
				m -= t;
			}

			for (int i = 0; i < std::min(2 * n, m); i++) {
				long long max = 0, pos = -1;
				bool first = false;
				merge(put);
				for (int j = 0; j < n; j++) {
					long long len = calc({v[j].first, v[j].first + k - 1});
					if (len > max) {
						pos = j;
						first = true;
						max = len;
					}
					len = calc({v[j].second, v[j].second + k - 1});
					if (len > max) {
						pos = j;
						first = false;
						max = len;
					}
				}
				if (pos == -1) break;
				ans += max;
				pair tmp{v[pos].first, v[pos].first + k - 1};
				if (!first) tmp = {v[pos].second, v[pos].second + k - 1};
				put.push_back(tmp);
			}
			tans = std::max(tans, ans);
		}
		std::cout << tans << '\n';
	}
}

